class Solution {
public:
    vector<vector<string>> ret;
    vector<string> path;//记录某一次dfs的结果
    vector<bool> col;//记录这一列是否存在皇后
    vector<bool> dis1;//记录正对角线上是否存在皇后
    vector<bool> dis2;//记录副对角线上是否存在皇后
    void dfs(int index,int size)
    {
        if(index==size)
        {
            ret.push_back(path);
            //储存答案
            return;
        }
        //从第index这一行的位置中选择一个位置放n皇后
        for(int i = 0;i<size;i++)
        {
            if(!col[i]&&!dis1[index+i]&&!dis2[index-i+size])
            {
                string tmp;
                for(int j = 0;j<size;j++)
                {
                    if(j == i)
                    {
                        tmp+='Q';
                    }
                    else
                    {
                        tmp+='.';
                    }
                }
                path.push_back(tmp);
                col[i] = true;
                dis1[index+i] = true;
                dis2[index-i+size] = true;
                dfs(index+1,size);//递归处理下一层
                //恢复现场
                col[i] = false;
                dis1[index+i] = false;
                dis2[index-i+size] = false;
                path.pop_back();
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        col.resize(n,false);
        dis1.resize(2*n+1,false);
        dis2.resize(2*n+1,false);
        dfs(0,n);
        return ret;
    }
};